package algorithm.leetcode.medium;

/*
 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 */

import java.util.Arrays;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/30
 */
public class Question120 {

    public static void main(String[] args) {

    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }

        int r = triangle.size();
        int c = triangle.get(r - 1).size();
        int[][] dp = new int[r][c];
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < r; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }

        for (int j = 1; j < r; j++) {
            int n = 1;
            while (n < triangle.get(j).size() - 1) {
                dp[j][n] = Math.min(dp[j - 1][n - 1], dp[j - 1][n]) + triangle.get(j).get(n);
                n++;
            }
            dp[j][n] = dp[j - 1][n - 1] + triangle.get(j).get(n);
        }
        return Arrays.stream(dp[c - 1]).min().getAsInt();

    }
}
